# 定义图的类
class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def dfs(self, start_vertex):
        # 初始化访问标记数组
        visited = [False] * self.num_vertices
        # 调用递归的DFS方法
        self._dfs_recursive(start_vertex, visited)

    def _dfs_recursive(self, current_vertex, visited):
        # 标记当前节点为已访问
        visited[current_vertex] = True
        print(current_vertex, end=" ")

        # 遍历当前节点的所有邻居
        for neighbor in self.adj_list[current_vertex]:
            if not visited[neighbor]:
                # 递归调用DFS
                self._dfs_recursive(neighbor, visited)

# 示例图的构建
num_vertices = 6
graph = Graph(num_vertices)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)

# 从节点0开始进行DFS遍历
print("DFS traversal starting from vertex 0:")
graph.dfs(0)